package _2022.hot100._94_二叉树的中序遍历;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @author： YHSimon
 * @date： 2022-04-22 11:50
 */
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(){}
    TreeNode(int val){this.val=val;}
    TreeNode(int val,TreeNode left,TreeNode right){
        this.val=val;
        this.left=left;
        this.right=right;
    }

}
public class Solution {

    //迭代 实质模拟栈
    public List<Integer> inorderTraversal2(TreeNode root){
        List<Integer> res=new ArrayList<>();
        Deque<TreeNode> stk=new LinkedList<>();
        while(root!=null||!stk.isEmpty()){
            while(root!=null){
                stk.push(root);
                root=root.left;
            }
            root=stk.pop();
            res.add(root.val);
            root=root.right;
        }
        return res;
    }
    //递归
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> ans=new ArrayList<>();
        inList(ans,root);
        return ans;
    }

    private void inList(List<Integer> ans, TreeNode node) {
        if(node==null){
            return;
        }
        if(node.left!=null){
            inList(ans, node.left);
        }
        ans.add(node.val);
        if(node.right!=null){
            inList(ans, node.right);
        }
    }

    public static void main(String[] args) {
        TreeNode root=new TreeNode(1,null,new TreeNode(2,new TreeNode(3),null));

        Solution s = new Solution();
        System.out.println(s.inorderTraversal(root));
    }
}
